#pragma once

#include <cstdio>
#include <utility>
#include <vector>
#include <cassert>
#include <limits>
#include <string>

void fatal(const char*, ...);

class Graph {
public:

	// NodeId is an interger type that can be used
	// to store node IDs.
	typedef unsigned short NodeId;

	// MaxNode is the maximum number of nodes.
	static const unsigned int MaxNode;

	// MaxPeople is the maximum number of
	// nodes with people on them.
	static const unsigned int MaxPeople;

	// Node is as node in the topological graph.
	struct Node {
		// Id is the node's unique ID value corresponding
		// to its index in the nodes vector of the domain.
		NodeId id;

		// P is the index into the people array of the
		// people at this node.
		int p;

		// Out is the ID of each successor via an out-going arc.
		std::vector<int> out;
	};

	// A People cuples a number of injured people along
	// with the node at which they reside.
	struct People {
		People(unsigned int nu, int nd) : num(nu), node(nd) { }

		// Num is the number of people in this group.
		unsigned int num;

		// nd is the graph node containing the people.
		NodeId node;
	};

	// This constructor creates a graph with the given
	// number of nodes, but no edges.
	Graph(unsigned int n);

	// This constructor creates a Graph domain
	// by reading the graph description and location
	// of injured people from the given file.
	Graph(FILE*);

	// Addedge adds an edge to the graph.
	void addedge(int src, int dst, double cost);

	// Addperson adds a person to a node.
	void addperson(int node);

	// Nodes is a vector of all nodes in the graph.
	std::vector<Node> nodes;

	// Adj is the adjacency matrix representation of the graph.
	std::vector<double> adj;

	// People is all sets of injured people at the different
	// nodes of the graph.
	std::vector<People> people;

	// precompute pre-computes the shortest path
	// information from the given node to all other
	// nodes in the graph.
	void precompute(int);

	// Shortest contains both closed list and open list
	// information for pre-computing shortest paths
	// between nodes of the graph.
	struct Shortest {
		Shortest();

		long i;
		int id, parent;
		double dist;

		// Setind sets the i field.  It is required for
		// to implement the Ops class for BinHeap.
		static void setind(Shortest*, long);

		// Pred returns true if the first argument
		// has a smalle dist than the second. It
		// is required for to implement the Ops class
		// for BinHeap.
		static bool pred(const Shortest*, const Shortest*);
	};

	// Shortest contains the shortest path information
	// between some distinguished nodes an the rest
	// of the graph.
	std::vector< std::vector<Shortest> > shortest;

private:
	// Init initializes the graph to have the given
	// number of nodes.
	void init(unsigned int n);
};
